package pers.qianyu.month_202012.date_20201201;

/**
 * 583. 两个字符串的删除操作
 * https://leetcode-cn.com/problems/delete-operation-for-two-strings/
 *
 * @author mizzle rain
 * @date 2020-12-01 21:20
 */
public class MinDistance {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int k = 1; k < dp[i].length; k++) {
                if (word1.charAt(i - 1) == word2.charAt(k - 1)) {
                    dp[i][k] = dp[i - 1][k - 1];
                } else {
                    dp[i][k] = Math.min(dp[i - 1][k] + 1, dp[i][k - 1] + 1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }

    public static void main(String[] args) {
        String w1 = "";
        String w2 = "a";
        int result = new MinDistance().minDistance(w1, w2);
        System.out.println("result = " + result);
    }
}
